Many specialized terms and abbreviations are used in the communications arts. At least some of the following are referred to within the text that follows, such as in this background and/or the description sections. Accordingly, the following terms and abbreviations are herewith defined:
4-QAM 4-Quadrature Amplitude Modulation
ARQ Automatic Repeat Request
AWGN Additive White Gaussian Noise
BPSK Binary Phase Shift Keying
CBR Coded Bi-directional Relaying
CRC Cyclical Redundancy Checking
CS Composite Signal
DPC Dirty Paper Coding
FEC Forward Error Correction
GF Galois Field
MRC Maximum Ratio Combining
MU-ARQ Multi-User ARQ
NACK Negative ACKnowledgment
NC Network Coding
OFDM Orthogonal Frequency Division Multiplexing
OFDMA Orthogonal Frequency Division Multiple Access
PAM Pulse Amplitude Modulated (signal)
PSK Phase Shift Keying
SINR Signal-to-Interference Noise Ratio
SNR Signal-to-Noise Ratio
Data, voice, multimedia, and other communications are the foundation of the modern information-oriented world. Such information is typically communicated over a network or networks. These networks may be public or private, packet-switched or circuit-switched, wireless or wired, some combination thereof, and so forth. Networks may operate under any of many different protocols and standards. Regardless, most networks include multiple nodes that each receive a communication from one node and then forward or otherwise transmit the communication to another node to propagate the information.
The communication of a set of related information pieces over a network is typically termed an information flow. The information flow is transmitted from node to node over the network. An information flow may be propagated over a single network or over multiple networks of the same or different types.
Traditionally, the coding of information for security, redundancy, bandwidth efficiency, or other reasons has been performed at the information flow level. Routing of information over the nodes of a network, on the other hand, has been performed at the network level. Thus, there has traditionally been a separation of coding to the information flow level and routing to the network level. This separation, however, may be changed in accordance with the concept of network coding.
The concept of network coding is relatively recent—it was first introduced in 2000. Network coding has the potential to improve communication in networks, both fixed networks and wireless networks. Theoretically, fixed/wired networks are free in principle of both noise and errors. (In reality, fixed networks may suffer from either or both of noise and errors.) Wireless networks, on the other hand, are commonly modeled with noise and interference that are individually and jointly capable of inducing errors in communications.
Generally, performing network coding involves mixing different pieces of information from different flows. This means that the notion of coding, which is historically performed on a link or flow level, is being moved up to the network level where multiple links and flows exist. A classical example illustrating network coding is from a seminal network coding paper entitled “Network Information Flow” and published in 2000 by R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung in IEEE Transactions on Information Theory (IT-46, pp. 1204-1216, 2000). This classical example is shown in FIG. 1.
FIG. 1 is an example network diagram 100 in which a conventional approach to network coding is implemented among communication nodes. As illustrated, network diagram 100 includes six communication nodes: a, b, c, d, e, and f. There are two information flows: A and B. The two sources of the information flows are nodes a and b. The two destinations for the information flows are nodes e and f.
Network diagram 100 illustrates how the two source nodes a and b initiate the info A and B, respectively, into the network. Both info A and info B are ultimately to be sent to both of the two destination nodes e and f. Node a transmits info A to node e. Node b transmits info B to node f.
The source nodes a and b also transmit info A and info B, respectively, to an intermediate node c. Node c creates a modulo sum A+B from info A and info B. The modulo sum may be created, for example, from a modulo-2 operation. A modulo-2 operation is equivalent to a bitwise exclusive OR (XOR) operation. This creation of a modulo sum is an encoding part of a conventional network coding operation.
Intermediate node c then forwards the modulo sum A+B to nodes e and f. As shown, the modulo sum A+B is forwarded to nodes e and f indirectly via another intermediate node d. After receiving the modulo sum A+B from node c, node d forwards it to both node e and node f. Because node e already knows info A, node e can determine info B from the modulo sum A+B. Similarly, node f can determine info A from the modulo sum A+B because it already knows info B. The retrieval of info B from the modulo sum A+B by node e using info A and the retrieval of info A from the modulo sum A+B by node f using info B are decoding parts of a conventional network coding operation.
By sending the packet with the modulo sum A+B, instead of individual packets for info A and info B in turn, it can be shown that the throughput may be increased and that the delay may be decreased. Thus, increasing throughput and/or decreasing delays in a network are benefits that may be attained when implementing network coding generally.
The example above performs conventional network coding using encoding and decoding operations having an XOR functionality, which is a modulo-2 operation. However, network coding has also been extended to addition in larger field sizes, at least in randomized settings.
Other advancements have been developed in network coding since its introduction in 2000. For example, a relationship between dirty paper coding (DPC) and network coding operations has been drawn by Peter Larsson et al. This relationship is explained further in two Published PCT Patent Applications to Peter Larsson, who is the inventor of the instant Patent Application, and two co-inventors Niklas Johansson and Kai-Erik Sunell. These two PCT Patent Applications are: [1] PCT Published Application No. WO 2006/071187, entitled “Method and Arrangement for Bi-Directional Relaying in Wireless Communication Systems” and published on 6 Jul. 2006 by applicant Telefonaktiebolaget L M Ericsson and [2] PCT Published Application No. WO 2007/008123, entitled “Method and Arrangement for Coding and Scheduling in Packet Data Communication Systems” and published on 18 Jan. 2007 by applicant Telefonaktiebolaget L M Ericsson. The former Application addresses coded bi-directional relaying (CBR), and the latter Application addresses Multi-User ARQ (MU-ARQ).
In these Published PCT Patent Applications, there is description that the encoding and decoding operations need not be based solely on finite fields. Instead, a linear additive modulus operation may be employed for encoding and decoding operations. More precisely, assuming two random variables x1 and x2 that are uniformly distributed over [−½, ½], the encoding operation may be y=(x1+x2) mod Λ. The corresponding decoding operation, e.g. for x1, may be (y−x2) mod Λ=x1.
The mod Λ in this instance (e.g., with Λ=1) means that for any value larger than ½ or less than −½, a suitable integer number is subtracted or added, respectively, to fold the resulting number into the range [−½, ½]. Although the linear additive modulus operation is described here in terms of one dimension, it is not limited to a single dimension.
Despite advancements in the field of network coding since its introduction in 2000, a number of deficiencies or weaknesses remain. For example, although existing network coding operations (e.g., finite field summations and the additive modulus operation) work fairly well in certain situations, they are a bit tricky to use in other situations. For instance, existing implementations of network coding can be finicky in noisy channels. Firstly, classical network coding operations with finite fields are intended to be used on forward error correction (FEC) decoded, error-free messages.
Secondly, with the additive modulus operation for encoding and decoding, a network coding implementation may operate on noisy baseband signals prior to FEC decoding. However, the decoding node benefits more from ascertaining precise channel states in order to do a “perfect” cancellation of the undesired, but “known” interfering signal. This precise knowledge and perfect cancellation can be difficult to achieve in real-world implementations.
Thus, deficiencies and weaknesses of conventional network coding include needing FEC-decoded, error-free messages and needing precise knowledge of interfering signals and perfect cancellation thereof in noisy environments to achieve a given level of service. These deficiencies and weaknesses, as well as other drawbacks of conventional network coding, are addressed by one or more of the various embodiments of the present invention.